def bubble_sort(arr):
    """
    冒泡排序基础版本
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n):
        # 每次遍历，最大的元素会"冒泡"到最后
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                # 交换相邻元素
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr







def bubble_sort_optimized(arr):
    """
    冒泡排序优化版本（添加交换标志）
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # 如果这一轮没有发生交换，说明已经有序
        if not swapped:
            break
    return arr






def selection_sort(arr):
    """
    选择排序基础版本
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n):
        # 找到未排序部分的最小元素
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # 将最小元素交换到已排序部分的末尾
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr








def selection_sort_optimized(arr):
    """
    选择排序优化版本（同时找最小和最大元素）
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n//2):
        min_idx, max_idx = i, i
        for j in range(i, n-i):
            if arr[j] < arr[min_idx]:
                min_idx = j
            if arr[j] > arr[max_idx]:
                max_idx = j
        # 将最小元素放到前面
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        # 如果最大元素原来在i位置，现在被移动到了min_idx位置
        if max_idx == i:
            max_idx = min_idx
        # 将最大元素放到后面
        arr[n-i-1], arr[max_idx] = arr[max_idx], arr[n-i-1]
    return arr






def selection_sort_optimized(arr):
    """
    选择排序优化版本（同时找最小和最大元素）
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n//2):
        min_idx, max_idx = i, i
        for j in range(i, n-i):
            if arr[j] < arr[min_idx]:
                min_idx = j
            if arr[j] > arr[max_idx]:
                max_idx = j
        # 将最小元素放到前面
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        # 如果最大元素原来在i位置，现在被移动到了min_idx位置
        if max_idx == i:
            max_idx = min_idx
        # 将最大元素放到后面
        arr[n-i-1], arr[max_idx] = arr[max_idx], arr[n-i-1]
    return arr





def selection_sort_optimized(arr):
    """
    选择排序优化版本（同时找最小和最大元素）
    :param arr: 待排序的列表
    :return: 排序后的列表
    """
    n = len(arr)
    for i in range(n//2):
        min_idx, max_idx = i, i
        for j in range(i, n-i):
            if arr[j] < arr[min_idx]:
                min_idx = j
            if arr[j] > arr[max_idx]:
                max_idx = j
        # 将最小元素放到前面
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        # 如果最大元素原来在i位置，现在被移动到了min_idx位置
        if max_idx == i:
            max_idx = min_idx
        # 将最大元素放到后面
        arr[n-i-1], arr[max_idx] = arr[max_idx], arr[n-i-1]
    return arr


import time
import random


def test_sort_algorithm(sort_func, arr_size=1000):
    """
    测试排序算法的性能
    :param sort_func: 排序函数
    :param arr_size: 测试数组大小
    """
    # 生成随机测试数据
    test_data = [random.randint(0, 10000) for _ in range(arr_size)]
    data_copy = test_data.copy()

    print(f"\n测试 {sort_func.__name__} (数组大小: {arr_size})")

    # 测试排序时间
    start_time = time.perf_counter()
    sorted_data = sort_func(data_copy)
    end_time = time.perf_counter()

    # 验证排序结果是否正确
    is_sorted = all(sorted_data[i] <= sorted_data[i + 1] for i in range(len(sorted_data) - 1))

    print(f"排序耗时: {end_time - start_time:.6f}秒")
    print(f"排序验证: {'成功' if is_sorted else '失败'}")







# 测试小数组
small_data = [5, 3, 8, 4, 2]
print("原始数据:", small_data)
print("冒泡排序结果:", bubble_sort(small_data.copy()))
print("优化冒泡排序结果:", bubble_sort_optimized(small_data.copy()))
print("选择排序结果:", selection_sort(small_data.copy()))
print("优化选择排序结果:", selection_sort_optimized(small_data.copy()))

# 性能测试
test_sort_algorithm(bubble_sort, 1000)
test_sort_algorithm(bubble_sort_optimized, 1000)
test_sort_algorithm(selection_sort, 1000)
test_sort_algorithm(selection_sort_optimized, 1000)

# 更大规模的测试
test_sort_algorithm(bubble_sort_optimized, 5000)
test_sort_algorithm(selection_sort_optimized, 5000)


class Student:
    def __init__(self, name, score):
        self.name = name
        self.score = score

    def __repr__(self):
        return f"Student(name='{self.name}', score={self.score})"

    # 为了简化比较操作，我们可以定义__lt__方法
    def __lt__(self, other):
        return self.score < other.score


def bubble_sort_students(students):
    """
    对学生对象列表按成绩进行冒泡排序（升序）
    :param students: 学生对象列表
    :return: 排序后的列表
    """
    n = len(students)
    for i in range(n):
        swapped = False
        for j in range(0, n-i-1):
            # 比较学生成绩
            if students[j].score > students[j+1].score:
                # 交换学生对象位置
                students[j], students[j+1] = students[j+1], students[j]
                swapped = True
        if not swapped:
            break
    return students



def selection_sort_students(students):
    """
    对学生对象列表按成绩进行选择排序（升序）
    :param students: 学生对象列表
    :return: 排序后的列表
    """
    n = len(students)
    for i in range(n):
        # 找到未排序部分成绩最低的学生索引
        min_idx = i
        for j in range(i+1, n):
            if students[j].score < students[min_idx].score:
                min_idx = j
        # 将找到的最小元素交换到已排序部分的末尾
        students[i], students[min_idx] = students[min_idx], students[i]
    return students






def selection_sort_students(students):
    """
    对学生对象列表按成绩进行选择排序（升序）
    :param students: 学生对象列表
    :return: 排序后的列表
    """
    n = len(students)
    for i in range(n):
        # 找到未排序部分成绩最低的学生索引
        min_idx = i
        for j in range(i+1, n):
            if students[j].score < students[min_idx].score:
                min_idx = j
        # 将找到的最小元素交换到已排序部分的末尾
        students[i], students[min_idx] = students[min_idx], students[i]
    return students


def quick_sort_students(students):
    """
    对学生对象列表按成绩进行快速排序（升序）
    :param students: 学生对象列表
    :return: 排序后的列表
    """
    if len(students) <= 1:
        return students

    pivot = students[len(students) // 2]
    left = [s for s in students if s.score < pivot.score]
    middle = [s for s in students if s.score == pivot.score]
    right = [s for s in students if s.score > pivot.score]

    return quick_sort_students(left) + middle + quick_sort_students(right)



# 创建测试数据
students = [
    Student("张三", 85),
    Student("李四", 92),
    Student("王五", 78),
    Student("赵六", 90),
    Student("钱七", 85),
    Student("孙八", 88)
]

print("原始学生列表:")
for student in students:
    print(student)

# 测试冒泡排序
print("\n冒泡排序结果:")
bubble_sorted = bubble_sort_students(students.copy())
for student in bubble_sorted:
    print(student)

# 测试选择排序
print("\n选择排序结果:")
selection_sorted = selection_sort_students(students.copy())
for student in selection_sorted:
    print(student)

# 测试快速排序
print("\n快速排序结果:")
quick_sorted = quick_sort_students(students.copy())
for student in quick_sorted:
    print(student)

# 测试内置排序
print("\n内置sorted排序结果:")
builtin_sorted = sorted(students, key=lambda x: x.score)
for student in builtin_sorted:
    print(student)
















# 创建测试数据
students = [
    Student("张三", 85),
    Student("李四", 92),
    Student("王五", 78),
    Student("赵六", 90),
    Student("钱七", 85),
    Student("孙八", 88)
]

print("原始学生列表:")
for student in students:
    print(student)

# 测试冒泡排序
print("\n冒泡排序结果:")
bubble_sorted = bubble_sort_students(students.copy())
for student in bubble_sorted:
    print(student)

# 测试选择排序
print("\n选择排序结果:")
selection_sorted = selection_sort_students(students.copy())
for student in selection_sorted:
    print(student)

# 测试快速排序
print("\n快速排序结果:")
quick_sorted = quick_sort_students(students.copy())
for student in quick_sorted:
    print(student)

# 测试内置排序
print("\n内置sorted排序结果:")
builtin_sorted = sorted(students, key=lambda x: x.score)
for student in builtin_sorted:
    print(student)